nLab ultrafilter

Definitions

An ultrafilter on a set $S$ is a collection $F$ of subsets of $S$ satisfying the axiom

$$A \in F \;\Leftrightarrow\; \forall (B_1, \ldots, B_n \in F),\; \exists (x \in A \cap B_1 \cap \cdots \cap B_n) .$$

This is the only axiom necessary; from this, you can prove that $F$ is a filter. Alternatively, if we start by requiring $F$ to be a filter, then we need add only the axiom

$$A \in F \;\Leftrightarrow\; \forall B \in F,\; \exists x \in A \cap B .$$

Or if we start by requiring $F$ to be a proper filter, then we need only the $\Leftarrow$ half of this latter axiom.

We may also define an ultrafilter to be maximal among the proper filters. This definition generalises from the power set of $S$ to any poset $L$; notice that we speak of an ultrafilter on $S$ but an ultrafilter in $L$. In a distributive lattice, every ultrafilter is prime; the converse holds in a Boolean algebra.

Using excluded middle, it is equivalent to say that a filter $F$ on $S$ is an ultrafilter if, given any subset $A$ of $S$, either $A$ or its complement belongs to $F$; this version generalises to any Boolean algebra. Another way to define an ultrafilter in a Boolean algebra $L$ is as a Boolean-algebra homomorphism from $L$ to the set $\{\bot,\top\}$ of Boolean truth values.

Given an element $x$ of a set $S$, the principal ultrafilter (on $S$) at $x$ consists of every subset of $S$ to which $x$ belongs. An ultrafilter $F$ is fixed if the intersection of its elements is inhabited, in which case that intersection must be a singleton $\{x\}$ and $F$ is the principal ultrafilter at $x$.

In contrast, if this intersection empty, then we call $F$ a free ultrafilter. It is possible, if one denies the axiom of choice, that every ultrafilter of subsets is fixed. In contrast, the ultrafilter principle (a weak form of the axiom of choice) states that any proper filter (in any Boolean lattice) may be extended to an ultrafilter. Then any infinite set has a free proper filter (such as the filter of cofinite subsets) and so a free ultrafilter.

Free ultrafilters are important in nonstandard analysis and model theory, where the ultrafilter principle seems to be a necessity.

Category-theoretic interpretations

There are in fact many interrelated ways of defining ultrafilters. We present a few here.

Ultrafilters form a monad

For any set $X$, let $U X$ be the set of ultrafilters on $X$. Principal ultrafilters provide an inclusion $\eta\colon X\to U X$, which turns out to be the unit of a monad on $Set$, as briefly touched upon above. The multiplication can be described fairly explicitly. First of all, if $A\subseteq X$, define $[A]\subseteq U X$ to be the set of all ultrafilters containing $A$. Then given $\mathcal{F} \in U U X$, i.e. an ultrafilter of ultrafilters, we let $\mu(\mathcal{F}) = \{ A | [A] \in \mathcal{F} \}$; one can verify that this is an ultrafilter and makes $U$ into a monad. This monad is traditionally denoted $\beta$.

The ultrafilter monad can also be described as follows. The 2-element set carries a unique structure of Boolean algebra internal to the category of sets. When thus cast in the role of dualizing object, it induces an adjoint pair of functors

$$(Set \stackrel{P = Set(-, \mathbf{2})^{op}}{\to} Bool^{op}) \; \; \dashv \; \; (Bool^{op} \stackrel{Bool(-, \mathbf{2})}{\to} Set)$$

whose corresponding monad $Bool(P -, \mathbf{2})$ is canonically identified with the ultrafilter monad $\beta$. Another description (due to Kennison and Gildenhuys) is that it is the codensity monad induced from the full embedding $Fin \hookrightarrow Set$ of finite sets into $Set$. See Leinster for a full account, and some extensions.

Ultrafilters and coproducts

Observe that the canonical map

$$\beta(X) + \beta(Y) \to \beta(X + Y)$$

is an isomorphism (for, each ultrafilter $U$ on $X + Y$ must contain exactly one of $X, Y$; if it contains $X$, then it is generated by the ultrafilter on $X$ given by $\{X \cap A: A \in U\}$).

Theorem (R. Börger)

The endofunctor $\beta$ is terminal among endofunctors $Set \to Set$ that preserve finite coproducts.

A topological proof of this fact has been given by Richter (see references).

This gives one universal characterization of the ultrafilter endofunctor. This theorem implies that there is precisely one monad structure on $\beta$, and that if $F\colon Set \to Set$ is a monad which preserves finite coproducts, then the unique transformation $F \to \beta$ is a morphism of monads.

Ultrafilters and presheaves

Theorem

(Garner, 2018.) The category of endofunctors $Set \to Set$ that preserve finite coproducts is equivalent to the category of presheaves of sets on the Blass category $U F$ of ultrafilters. The ultrapower functor with respect to an ultrafilter $U$ corresponds to the representable functor of $U$.

The Blass category of ultrafilters has as objects, pairs of a set $X$ and an ultrafilter $\mathcal{U}$ of $\beta X$. Morphisms from $(X, \mathcal{U})$ to $(Y, \mathcal{V})$ are $=_{\mathcal{U}}$-equivalence classes of partial continuous maps defined on a set in $\mathcal{U}$, continuity here meaning that for any $V \in \mathcal{V}$, $f^{-1}(V) \in \mathcal{U}$.

Ultrafilters and codensity

Another known universal characterization of the ultrafilter monad is via the concept of codensity monads. (This fact was recently (June 2011) mentioned by Tom Leinster at the categories list, but it also appears sparsely in the literature; see for instance Algebraic Theories, exercise 3.2.12(e).)

Let $i: Fin \to Set$ be the usual full inclusion of finite sets into sets. The restricted Yoneda embedding

$$Set \stackrel{y^{op}}{\to} (Set^{Set})^{op} \stackrel{(Set^i)^{op}}{\to} (Set^{Fin})^{op},$$

taking a set $X$ contravariantly to the functor $Set(X, i-)$, has a right adjoint

$$Set^{Fin}(-, i): (Set^{Fin})^{op} \to Set$$

(Note: this construction is dual to the familiar Kan construction?, which takes as input a functor $F: A \to C$ from a small category to a cocomplete category, and produces as output an adjoint pair whose right adjoint is a functor $C \to Set^{A^{op}}$; see for instance nerve and realization.)

The composite of these functors gives a monad $Set \to Set$ which in fact is just the ultrafilter monad:

$$\beta \cong Set^{Fin}(Set(X, i-), Set(1, i-))$$

One way of considering the codensity monad formulation is that the ultrafilter functor is terminal among endofunctors whose restriction to the category of finite sets is the identity functor. This likewise gives the uniqueness of the monad structure, as well as the fact that $\beta$ is the terminal monad that restricts to $1_{Fin}$.

Ultrafilters and unbiased Boolean algebras

The codensity monad description is related to the traditional description in terms of Boolean algebras; to see this more clearly, it helps to pass to unbiased Boolean algebras, which are equivalent to Boolean algebras.

Recall that an unbiased Boolean algebra is a product-preserving functor

$$Fin_+ \to Set$$

where $Fin_+$ is the category of inhabited finite sets. If $X$ is any set, there is an unbiased Boolean algebra

$$Set(X, i_+ -): Fin_+ \to Set$$

which may be called the unbiased power set. (Here $i_+: Fin_+ \to Set$ denotes the standard inclusion.) We may denote this by $(-)^X$ for short. The inclusion functor $i_+$ is identified with $(-)^1$, and corresponds to the Boolean algebra $2$.

Definition

An ultrafilter on $X$ is a natural transformation $(-)^X \to (-)^1$ in the category $Prod(Fin_+, Set)$.

Of course this is the same as a natural transformation $(-)^X \to (-)^1$ in the usual functor category $Set^{Fin_+}$. Such transformations are in bijection with transformations

$$Set(X, i-) \to Set(1, i-)$$

in $Set^{Fin}$ used in the codensity monad description of ultrafilters.

Ultrafilters via other algebraic theories

There are other descriptions of ultrafilters, based on $k$-valued Post algebras. Recall the proposition there:

• Let $M_k$ be the monoid of endofunctions on a $k$-element set, for a finite set of cardinality $k \geq 3$. The forgetful functor $U_k: BoolAlg \to M_k\text{-}Set$ is full and faithful.

Let us take for example $k = 3$. Given a set $X$, the functor $U_3$ takes the unbiased Boolean algebra $Set(X, i_+ -)$ to the set $Set(X, 3) = 3^X$, regarded as a set equipped with the canonical (pointwise) action of $Set(3, 3) = M_3$. It takes an ultrafilter on $X$, i.e., an unbiased Boolean algebra map

$$Set(X, i_+ -) \to Set(1, i_+ -),$$

to a morphism of $M_3$-sets

$$Set(X, 3) \to 3.$$

The proposition implies that the mapping

$$\beta(X) \to M_3\text{-}Set(3^X, 3)$$

is a natural bijection, giving us another way of viewing ultrafilters on $X$, this time involving only unary operations.

This is of course another codensity monad description in disguise; this time the codensity monad is induced by the full inclusion

$$B M_3 \to Set$$

of the category of endofunctions on the 3-element set into the category of sets. The results of this section say that the ultrafilter monad is the codensity monad for this particular inclusion.

In a post to the categories list (see references), Bill Lawvere remarks that large cardinal hypotheses can be formulated as obstructions to similar codensity monads being isomorphic to the identity. For example, the existence of infinite sets is equivalent (assuming the ultrafilter principle) to the fact that $\beta$ is not isomorphic to the identity. Or, for the full inclusion

$$M_{\mathbb{N}} \to Set$$

the existence of an uncountable measurable cardinal is equivalent (in ZFC) to the fact that the induced codensity monad is not isomorphic to the identity (i.e., the first uncountable measurable cardinal is where the first “jump” takes place). Lawvere gives a couple more examples of a more geometric nature.

Algebras of the ultrafilter monad

A theorem due to Ernest Manes is that the Eilenberg-Moore category of ultrafilter monad is the category of compact Hausdorff spaces with its obvious forgetful functor to $Set$.

• In one direction, if $X$ is a compact Hausdorff space, then the corresponding algebra structure

  $$\xi: \beta X \to X$$

  sends an ultrafilter $F$ on $X$ to the unique point in $X$ to which $F$ converges. ($F$ converges to $x$ if the filter of neighborhoods of $x$ is contained in $F$; see convergence space.)

• In the other direction, given an algebra structure $\xi\colon \beta X \to X$, we define a topology by defining a set $U \subseteq X$ to be open if

  $$\forall_{x \in X} \forall_{F \in \beta X} (x \in U \: and \: \xi(F) = x) \Rightarrow U \in F$$

  The sense of this is that a set is open if it is a neighborhood of each of its points, and the neighborhood filter of $x$ is the intersection of all ultrafilters that converge to $x$. (The unit condition is that

  $$\xi (prin(x)) = x$$

  so that the neighborhood filter of $x$ is contained in $prin(x)$, i.e., each neighborhood of $x$ contains $x$.) It is not hard to verify that this condition indeed defines a topology. In fact, the topology is compact Hausdorff, essentially because compactness is equivalent to having every ultrafilter converge to some point, and Hausdorffness to having that point be unique.

In particular, $\beta X$ can be equipped with a compact Hausdorff topology which is the free compact Hausdorff space generated by $X$, or equivalently the Stone-Čech compactification of the discrete topology on $X$.

The monad $\beta$ also extends to the bicategory $Rel$ of sets and binary relations. It was observed by Barr that the generalized multicategories defined relative to this extension can be identified with arbitrary topological spaces; see relational beta-module. Thus, compact Hausdorff spaces are to topological spaces as monoidal categories are to multicategories.

By exploiting the connection between monads and algebraic theories, it is possible to define a compact Hausdorff object in any category $C$ with small products, as a product-preserving functor

$$Kl(\beta)^{op} \to C$$

where $Kl(\beta)$ is the Kleisli category (or the full category of compact Hausdorff spaces whose objects are of the form $\beta S$).

Number of ultrafilters

If $X$ is a finite set, then all ultrafilters on $X$ are principal and the number of them is the cardinality of $X$.

If $X$ is an infinite set of cardinality $\kappa$, then the number of ultrafilters on $X$ is $2^{2^\kappa}$. A proof may be found at independent family of sets.

References

• R. Börger, Coproducts and Ultrafilters, JPAA 46 (1987) pp.35-47.

• E. Manes, Algebraic Theories, Graduate Texts in Mathematics 26, Springer-Verlag, 1976.

• G. Richter, Axiomatizing the Category of Compact Hausdorff Spaces, Categories at Work (ed. Herrlich and Porst), Heldermann-Verlag (1991), 199-215. (link)

• Tom Leinster, Post to the categories list. (link)

• Todd Trimble, Post to A Dialogue on Infinity. (link)

• Bill Lawvere, Post to the categories list. (link) archive, 21 Mar 2000

• Tom Leinster, Definition of ultrafilter. (blog post)

• Tom Leinster, Where do ultrafilters come from? (blog post)

• Tom Leinster, Codensity and the ultrafilter monad, TAC 28 (2013) pp.332-370. (TAC) arXiv:1209.3606.

• H. Volger, Ultrafilters, ultrapowers and finiteness in a topos, JPAA 6 (1975) pp.345-356.

• Richard Garner, Ultrafilters, finite coproducts and locally connected classifying toposes. arXiv:1808.08687.

• Jirí Adámek, Lurdes Sousa, D-Ultrafilters and their Monads. arxiv:1909.04950.